A programmable logic circuit, also referred to as field programmable gate array (FPGA) is an off the shelf integrated logic circuit which can be programmed by the user to perform logic functions. Circuit designers define the desired logic functions and the circuit is programmed to process the signals accordingly. Depending on logic density requirements and production volumes, programmable logic circuits are superior alternatives in terms of cost and time to market. A typical programmable logic circuit is composed of logic cells where each of the logic cells can be programmed to perform logic functions on its input variables. Additionally, interconnect resources are provided throughout the programmable logic circuit which can be programmed to conduct signals from outputs of logic cells to inputs of logic cells according to user specification.
As technology progresses to allow for larger and more sophisticated programmable logic circuits, both the number of logic cells and the required interconnect resources increases in the circuit. Competing with the increased number of logic cells and interconnect resources is the need to keep the circuit size small. One way to minimize the required circuit size is to minimize the interconnect resources while maintaining a certain level of connectivity. Therefore, it can be seen that as the functionality implemented on the chip increases, the interconnection resources required to connect a large number of signals can be quickly exhausted. The trade-offs are either to provide for a lower utilization of logic cells in a circuit while keeping the circuit size small or to provide more routing resources that can increase the circuit size dramatically.
There has been a progression of increasingly complex connection styles over the last forty years in the field of programmable logic circuits. L. M. Spandorfer in 1965 describes possible implementation of a programmable logic circuit using neighborhood interconnection, and connections through multiple conductors using switches in a Clos network. R. G. Shoup in his PhD thesis of 1970 describes both the use of a neighborhood interconnect and the use of a bus for longer distance interconnect.
Freeman in the U.S. Pat. No. 4,870,302 of 1989 describes a commercial implementation of a FPGA using neighborhood interconnects, short (length one, called single) distance interconnects, and global lines for signals such as clocks. The short distance interconnects interact with the inputs and outputs of logic cells where each input is connected through switches to every short wire neighboring to a logic cell and horizontal and vertical short wires connect through a switch box in a junction. El Gamal et al. in U.S. Pat. No. 4,758,745 introduces segmented routing where inputs and outputs of logic cells interact with routing segments of different lengths in one dimension.
Peterson et al. in U.S. Pat. No. 5,260,610 and Cliff et al. in U.S. Pat. No. 5,260,611 introduce a local set of conductors interfacing with a set of logic elements where every input of the logic elements is connected, through switches, to every local conductor in the set; additional chip length conductors are introduced both horizontally and vertically where the horizontal conductor can connect to the vertical conductors and the horizontal conductors connect to multiple local conductors. In U.S. Pat. No. 4,870,302, U.S. Pat. No. 4,758,745, U.S. Pat. No. 5,260,610, and U.S. Pat. No. 5,260,611, the input conductor of a logic cell has full connections to the set of local conductors (e.g. for n-inputs and k-local conductors, there is n×k switches connecting the inputs to the local conductors. A multiplexer (MUX) scheme may also be used so that the number of transistors is reduced). In U.S. Pat. No. 4,870,302, U.S. Pat. No. 4,758,745, U.S. Pat. No. 5,260,610, and U.S. Pat. No. 5,260,611, the general interconnect resources are limited to one or two different lengths (i.e. singles of U.S. Pat. No. 4,870,302, local and chip length in U.S. Pat. No. 5,260,610 and U.S. Pat. No. 5,260,611) or limited in one dimension (i.e. different lengths horizontally in U.S. Pat. No. 4,758,745, local vertically in U.S. Pat. No. 5,260,610 and U.S. Pat. No. 5,260,611).
Camarota et al. in U.S. Pat. No. 5,144,166 and Kean in U.S. Pat. No. 5,469,003 introduce a routing scheme with more than two different lengths in both dimensions with limitations in the reach of those conductors. While U.S. Pat. No. 5,144,166 allows each wire to be selectively driven by more than one possible driving source, U.S. Pat. No. 5,469,003 is limited to be unidirectional in that each wire is hardwired to a multiplexer output. The connectivity provided in both U.S. Pat. No. 5,144,166 and U.S. Pat. No. 5,469,003 are very low, based on the premises that either connections are neighborhood or relatively local, or logic cells itself can be used as interconnection resources instead of performing logic functions. Ting in U.S. Pat. No. 5,457,410, U.S. Pat. No. 6,507,217, U.S. Pat. No. 6,051,991 and U.S. Pat. No. 6,597,196 described a multiple level architecture where multiple lengths of conductors interconnect through switches in a hierarchy of logic cells.
Young et al. in U.S. 2001/0007428 and U.S. Pat. No. 5,914,616 describe an architecture with multiple lengths of wires in two dimensions (three in each dimension) where for short local connections, a near cross-bar scheme is used where a set of logic cells outputs are multiplexed to a reduced set of output ports which then interface to other interconnect resources. The longer wires generally fan-in into shorter length wires in a respective dimension. Reddy et al. in U.S. Pat. No. 6,417,694 discloses another architecture where inter-super-region, inter-region, and local conductors are used. A cross-bar scheme is used at the lowest level (using multiplexers) for the local wires to have universal access to the inputs of the logic elements. Reddy et al. in U.S. Pat. No. 5,883,526 discloses various schemes having circuit reduction techniques in the local cross-bar.
Reblewski et al. in U.S. Pat. No. 6,594,810 describes an architecture building a programmable logic circuit using crossbar devices recursively. Wong in U.S. Pat. No. 6,693,456 and U.S. Pat. No. 6,940,308 use Benes switching networks as the interconnection fabric for programmable logic circuit.
At the base level of circuit hierarchy, multiple-input Look Up Table (LUT) logic cells are commonly used. There are two advantages in using a LUT as the base logic cell. One advantage is that the LUT allows programmable implementation of any Boolean functions having up to the multiple-input and one output. Another advantage is that the multiple inputs are interchangeable and logically equivalent. Hence it does not matter which signal connecting to which input pin of the LUT for the LUT to function correctly as long as those signals connect to the respective inputs of the LUT.
A common problem to be solved in any programmable logic circuit is that of interconnectivity, namely, how to connect a first set of conductors carrying signals to a second multiple sets of conductors to receive those signals where the logic cells originating the signals and the logic cells receiving the signals are spread over a wide area in an integrated circuit (i.e., M number of outputs from M or less number of logic cells where one or more outputs of each logic cell connects to inputs of one or more logic cells). A conventional solution is to use a cross bar switch where every conductor of the first set is connectable to every conductor in the second multiple sets of conductors directly through a switch. Unfortunately, this approach is impractical in most cases. Prior solutions in one degree or another try to divide the connectivity problem into multiple pieces using a divide and conquer strategy where local clusters of logic cells are interconnected and extended to other clusters of logic, either through extensions of local connections or using longer distance connections. These prior interconnect schemes are ad hoc and mostly based on empirical experiences. A desired routing model or interconnect architecture should enable or guarantee full connectivity for a large number of inputs and outputs over a large part of the circuit all the time.
U.S. Pat. No. 6,975,139, U.S. Pat. No. 7,256,614 and U.S. Pat. No. 7,417,457 by the present inventors describe an L-level switching network (L-SN) which uses switches and L levels of intermediate conductors of I[i] number of conductors consisting of D[i] sets of conductors for i=[1:L] to connect a first plurality or set of M number of conductors to a second K sets of conductors of (K×N) number of conductors. The L-SN can be used as part of an interconnection fabric for a programmable logic circuit with much reduced switch counts and the number of switches used in the switching network is determined by a mathematical relations of the sizes of the first set of M number of conductors and the size and number of the second K sets of conductors of (K×N) number of conductors. The switching network, when limited to be a 1-SN or at the last intermediate stage or level in the conventional design, can have certain routing limits when at least one multicasting signal is logically grouped together with other signals from the first set of conductors in a skewed distribution. Thus, it is desirable to have an enhanced permutable switching network for programmable logic circuits where the routability or interconnectivity may be enhanced in the presence of multicasting signals independent of signal distribution while the cost of interconnections remains low in terms of number of switches and the software efforts in determining a place and route and the circuit layout implementation may be simplified.
One type of a L-level switching network (L-SN) which uses switches and L levels of intermediate conductors of I[i] number of conductors consisting of D[i] sets of conductors for i=[1:L] to connect a first plurality or set of M number of conductors to a second K sets of conductors of (K×N) number of conductors was first described by the present inventors in U.S. Pat. No. 6,975,139, U.S. Pat. No. 7,256,614 and U.S. Pat. No. 7,417,457. There are (L+2) levels of conductors in an L-SN: an 0-th level of conductors or pins of M or I[0] number of conductors or pins, i-th level of conductors of I[i] number of conductors consisting of D[i] sets of conductors for i=[1:L] and an (L+1)-th level of conductors or pins of K or D[L+1] sets of conductors of (D[L+1]×Πj=[1:L] D[j]) where each of the (i−1)-th level of conductors selectively couple to each of the D[i] sets of conductors of the i-th level of conductors through I[i−1] number of switches for i=[1:L+1] thus there are a total of Σi=[1:L+1] (I[i−1]×D[i]) number of switches in the conventional L-SN with N=Πj=[1:L] D[j]. The switching network, when limited to be a 1-SN or at the last intermediate stage or level in the conventional design, can have certain routing limits when at least one multicasting signal is logically grouped together with other signals from the first set of conductors in a skewed distribution.
Thus an L-level switching network (L-SN) of the conventional design has (L+2) levels of conductors and L levels of intermediate conductors of I[i] number of conductors consisting of D[i] sets of conductors for i=[1:L] and L≧1 to connect the 0-th level of pins or conductors of I[0] number of pins or conductors to the (L+1)-th level of pins or conductors of (D[L+1]×Πj=[1:L] D[j]) number of pins or conductors consisting of D[L+1] sets of pins or conductors through the L levels of intermediate conductors of the L-SN. A variable, DS[i], is defined as DS[i]=(I[i−1]/I[i])×D[i] for i=[1:L+1]. A DS[i]-tuple is DS[i] number of conductors of the (i−1)-th level of conductors with the characteristics that the DS[i]-tuple selectively couple to one conductor, through DS[i] number of switches, in each of the D[i] sets of conductors of the i-th level of conductors in an L-SN for i=[1:L+1]; additionally, in the L-SN, the I[i−1] number of conductors of the (i−1)-th level can be organized into (I[i−1]/DS[i]) number of DS[i]-tuples for i=[1:L+1].
FIG. 1A illustrates a conventional L-SN. In FIG. 1A, M is denoted as I[0] and K is denoted as D[L+1]. Furthermore, N=Πj=[1:L] D[j] where L=1, I[0]=16, I[1]=16, I[2]=24, D[1]=4, D[2]=6, for i=[1:L+1] and DS[i]=(I[i−1]/I[i])×D[i], there are (I[i−1]/DS[i]) groups of DS[i] number of conductors of the I[i−1] number of conductors of the (i−1)-th level of conductors and each group (the (I[i−1]/DS[i]) groups) of DS[i] number of conductors is denoted as a DS[i]-tuple where each DS[i]-tuple selectively couple to one conductor, through DS[i] number of switches, in each of the D[i] sets of conductors of the i-th level of conductors of I[i] number of conductors consisting of D[i] sets of conductors. It can be readily observed that the conventional L-SN example in FIG. 1A is drawn where each of the (I[i−1]/DS[i]) groups of DS[i]-tuples are consecutively labeled, e.g. first DS[i]-tuple is [101:104], second DS[i]-tuple is [105:108], third DS[i]-tuple is [109:112], (I[i−1]/DS[i])-th DS[i]-tuple is [113:116]; thus a DS[i]-tuple can be considered as DS[i] number of conductors that can be consecutively labeled in an L-SN representation and a X-tuple is X number of consecutively labeled conductors in the L-SN. Consider that there are eight nets carrying signals in the I[0] number of conductors [101:116] of FIG. 1A where the first four nets (101, 102, 103, 104) are in the first DS[1]-tuple, [101:104], and the next four nets (109, 110, 111, 112) are in the third DS[1]-tuple, [109:112], where the eight nets are selectively connected to the conductors in each of the D[L+1] sets of the (L+1)-th level of conductors of D[L+1] sets of conductors of (D[L+1]×Πj=[1:L] D[j]) number of conductors of the 1-SN (where D[L+1]=6 in the example of FIG. 1A): Specifically, given that net 101 has the connection specification represented as [1, 2, 3, 4], indicating a specified connection through one conductor in each of the first, the second, the third and the fourth sets of the D[L+1] sets ([151:156]) of the (L+1)-th level of conductors of D[L+1] sets of conductors of (D[L+1]×Πj=[1:L] D[j]) number of conductors connecting the pins of [F1:FK], thus the connection specifications connects net 101 to one conductor in each of the four sets of conductors of [151:154] which are respectively connected to the pins of [F1:F4], through the intermediate conductors [121:136] and the switches of the 1-SN. Additionally, each of the three nets (102, 103, 104) in the first DS[1]-tuple [101:104] has the same connection specification of [1] indicating connection to one conductor from 151 connecting respectively to F1 through the intermediate conductors [121:136] and the switches of the 1-SN. The other four nets (109, 110, 111, 112) of the third DS[1]-tuple, [109:112], where (109, 110, 111) has the connection specification of [2] which are to be selectively connected to the second set 152 of F2, with the remaining net 112 having the connection specification of [3], to be selectively coupled to the third set 153 of F3. Thus the eight nets are located within Y=2 number of DS[i]-tuples (e.g. two DS[i]-tuples [101:104] and [109:112]) and the number of source-conductors, SC, of the (i−1)-th level of conductors is equal to eight (the eight nets of ([101:104], [109:112]) where i=1 and the number of coupling-conductors, CC=Y×D[i]=8 of the i-th level of conductors (the eight conductors (121, 123, 125, 127, 129, 131, 133, 135)).
There are eleven connections to the pins of [F1:F4] of [F1:FK] (through [151:154] of [151:156]) to be made in order to completely connect or route the eight signals of the eight source-conductors using the 1-SN illustrated in FIG. 1A; there are at most eight coupling-conductors that can be selected from the D[1] sets of intermediate conductors of I[1] number of conductors: the eight coupling-conductors (121, 123, 125, 127, 129, 131, 133, 135) couple the eight source-conductors of the two DS[i]-tuples [101:104], [109:112] through the circled switches of the 1-SN, which in turn can only connect at most ten of the eleven connection specifications through [151:154] to the pins of [F1:F4] using the switches of the 1-SN. Thus the netlist interconnection specifications of the eight nets above can not be routed using the particular 1-SN. If there is no multicasting signal (e.g. net 101 is a single-casting signal such as connection specification of [1], instead of connection specification [1, 2, 3, 4]), any routing specifications (with single-casting signals) using the conventional 1-SN illustrated in FIG. 1A would not be a problem.
FIG. 1B is a redraw of FIG. 1A in the style represented in the U.S. Pat. No. 6,975,139, U.S. Pat. No. 7,256,614 and U.S. Pat. No. 7,417,457 and FIG. 1C is another redrawn illustration of FIG. 1A.
Note that in the illustrations of the embodiment of FIG. 1A, the number of coupling-conductors, CC of the i-th level of conductors connecting to any given number of source-conductors, SC, of the (i−1)-th level of conductors through (D[i]×I[i−1]) number of switches of the L-SN is CC=(Y×D[i]) where Y is the number of DS[i]-tuples of the (i−1)-th level of conductors the SC number of conductors are selected from.